/* 
 * 周教授讲授计算机算法课程，班上一共有72个学生。每一周，周教授都安排这些学生见一次面。
 * 有些周，周教授将72名学生分为每组8人，另外一些周，周教授将72名学生分为每组9人。
 * 只要两个学生被分在同一组，就算见一次面。周教授分组的原则是，在整个授课过程中，任意两
 * 个学生必须见一次面，且仅见一次面。问，周教授的课程需要安排多少周？周教授需要如何将这
 * 些学生分组？
 * 
 * 周教授有125名学生，将其分为25组，每组5名学生，周教授的课一共上31周。每一周，周教授
 * 让这些学生见一次面。如果算法课程结束时，任意两个学生恰好见了一次面，问，周教授如何分
 * 组？
 */

#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
#include <unordered_set>

#define STUDENT_NUM  125

class Relation
{
private:
    int meeted[STUDENT_NUM][STUDENT_NUM] = {0};

public:
    Relation()
    {
        for (int i = 0; i < STUDENT_NUM; i++) {
            meeted[i][i] = 1;
        }
    }

    void print()
    {
        printf("Meeted:\n");
        for (int i = 0; i < STUDENT_NUM; i++) {
            for (int k = 0; k < STUDENT_NUM; k++)
                printf("%3d", meeted[i][k]);
            printf("\n");
        }
    }

    bool solved()
    {
        for (int i = 0; i < STUDENT_NUM; i++) {
            for (int k = 0; k < STUDENT_NUM; k++)
                if (!meeted[i][k]) return false;
        }
        return true;
    }

    bool is_meeted(int a, int b)
    {
        return meeted[a][b];
    }

    void meet(int a, int b)
    {
        meeted[a][b] = 1;
        meeted[b][a] = 1;
    }

    void unmeet(int a, int b)
    {
        meeted[a][b] = 0;
        meeted[b][a] = 0;
    }
};

Relation relation;
class Group;
std::vector<Group *> solution;

// 分组类
class Group
{
private:
    int  group_size;                                // 分组大小
    int  group_num;                                 // 分组数
    int  student_num;                               // 学员人数
    std::vector< int >                     grouped;  // 学员i是否已经分组
    std::vector< std::unordered_set<int> >  groups;   // 学员分组方案

public:
    Group(int num, int size)
    {
        std::cout << "Enter new Group class." << std::endl;
        if (num % size != 0) {
            std::cout << "Invalid student num and group size!" << std::endl;
            assert(num % size == 0);
        }
        student_num = num;
        group_size  = size;
        group_num   = num / size;
        groups.resize(group_num);
        grouped.resize(num);
    }

    void print_group(int id)
    {
        printf("Group[%2d]:", id);
        for (auto item = groups[id].begin(); item != groups[id].end(); item++)
            printf("%4d", *item);
        printf("\n");
    }

    void print()
    {
        printf("Groups:\n");
        for (int i = 0; i < groups.size(); i++)
            print_group(i);
    }

    // 学员stud与group分组的成员是否见过面
    bool meeted_group(int group, int stud)
    {
        for (auto item = groups[group].begin(); item != groups[group].end(); item++) {
            if (relation.is_meeted(*item,stud)) return true;
        }
        return false;
    }

    void divide(int group_id, int remains)
    {
        //print();
        //printf("group %lu\n", groups[group_id].size());
        // 如果待分组的人数为0，说明本轮分组结束，进入下一轮分组
        // std::cout << "Enter divide group 1!" << std::endl;
        if (remains == 0) {
            relation.print();
            print();
            printf("\n\n");
            if (relation.solved()) {
                printf("Find solution:\n");
                for (int i = 0; i < solution.size(); i++) {
                    printf("Week %d:\n", i);
                    solution[i]->print();
                }
                return;
            }
            // std::cout << "Start next week divide group!" << std::endl;
            Group *next_group = new Group(student_num, 5);
            solution.push_back(next_group);
            next_group->divide(0, student_num);
            solution.pop_back();
            delete next_group;
            return;
        }
        // std::cout << "Enter divide group 2!" << std::endl;
        // 如果当前分组人数达到分组最大人数，进入下一组分组
        if (groups[group_id].size() == group_size) {
            // printf("Enter next divide group [%d]\n", group_id);
            // print();
            divide(group_id + 1, remains);
        }
        // 找一个未分组的学员加入当前分组
        // std::cout << "Enter divide group 3!" << std::endl;
        // print_group(group_id);
        for (int stud = 0; stud < student_num; stud++) {
            // 如果学员stud未分组，且与第group分组中所有成员均未见过面
            if (!grouped[stud] && !meeted_group(group_id, stud)) {
                // 将学员stud分到第group分组
                grouped[stud] = true;
                groups[group_id].insert(stud);
                // 将学员stud与本组学员置为已见面
                for (auto item = groups[group_id].begin(); item != groups[group_id].end(); item++)
                relation.meet(stud, *item);
                
                // 尝试下一个学员分组
                divide(group_id, remains - 1);
                // 回溯时还原
                grouped[stud] = false;
                groups[group_id].erase(stud);
                for (auto item = groups[group_id].begin(); item != groups[group_id].end(); item++)
                relation.unmeet(stud, *item);
            }
        }
    }
};

int main()
{
    Group *group = new Group(STUDENT_NUM, 5);
    solution.push_back(group);
    group->divide(0, STUDENT_NUM);
    solution.pop_back();
    delete group;
}